package primary.math;

/**
 * @Author Elephas
 * @Date 2022/1/9
 **/
public class CountPrimes {
    public static void main(String[] args) {
        countPrimes(10);
    }

    public static int countPrimes(int n){
        int count = 0;
        for(int i = 2; i < n ; i++){
            if(isPrime(i)){
                count++;
            }
        }
        return count;
    }
    static boolean isPrime(int n){
        int sqrt = (int) Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if(n % i == 0)
                return false;
        }
        return true;
    }

    /*
        解法二: 埃氏筛
     */
    public static int countPrimes2(int n){
        boolean[] isPrimes = new boolean[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            isPrimes[i] = true;
        }

        for (int i = 2; i < n; i++) {
            if(isPrimes[i]){
                count++;
                if( (long)i * i < n){
                    for (int j = i*i; j < n; j+=i) {
                        isPrimes[j]=false;
                    }
                }
            }
        }
        return count;
    }
}
